#include<iostream>
using namespace std;
void Merge(int arr[],int low,int mid,int high);
void MergeSort (int arr [], int low,int high) {
    if(low>=high) { return; } // 终止递归的条件，子序列长度为1
    int mid =  low + (high - low)/2;  // 取得序列中间的元素
    MergeSort(arr,low,mid);  // 对左半边递归
    MergeSort(arr,mid+1,high);  // 对右半边递归
    Merge(arr,low,mid,high);  // 合并
}
/*
        数组：   1 3 4 7 5 8 9 4 
        下标：   0 1 2 3 4 5 6 7 
        数组：   5 8 9 4
        下标：   4 5 6 7
        ⌈（7-4）/2⌉=1
*/
void Merge(int arr[],int low,int mid,int high)
{
    /*
    
    8 9 10
    1 3 4 5 7
    */
    //low为第1有序区的第1个元素，i指向第1个元素, mid为第1有序区的最后1个元素
    int i=low,j=mid+1,k=0;  //mid+1为第2有序区第1个元素，j指向第1个元素
    int *temp=new int[high-low+1]; //temp数组暂存合并的有序序列
    while(i<=mid&&j<=high){
        if(arr[i]<=arr[j]) //较小的先存入temp中
            temp[k++]=arr[i++];
        else
            temp[k++]=arr[j++];
    }
    while(i<=mid)//若比较完之后，第一个有序区仍有剩余，则直接复制到t数组中
        temp[k++]=arr[i++];
    while(j<=high)//同上
        temp[k++]=arr[j++];
    for(i=low,k=0;i<=high;i++,k++)//将排好序的存回arr中low到high这区间
	arr[i]=temp[k];
    delete []temp;//释放内存
}
int main()
{
    int len;
    cout<<"输入数组长度:";
    cin>>len;
    int num[len];
    cout<<"输入数组内容:";
    for(int i=0;i<len;i++)
    {
        cin>>num[i];
    }
    MergeSort(num,0,len-1);
    for(int i=0;i<len;i++)
    {
        cout<<num[i]<<' ';
    }
}
/*
8 4 5 7 1 3 6 2
*/